Integers are countable

Proof

We have the injection (actually bijection) \(\mathbb{Z} \to \mathbb{N}\) given by

Let \(m, n \in \mathbb{Z}\) such that \(f(n) = f(m)\). If \(m, n \geq 0\) then \(2n = 2m\), in which case \(m = n\). If \(m, n < 0\), then \(2|n| - 1 = 2|m| - 1\) so \(|n| = |m|\) but this means \(n = m\) since \(m\) and \(n\) have the same sign. These cases are exhaustive, since \(n < 0\) and \(m \geq 0\) means that \(f(n)\) is odd and \(f(m)\) is even. Thus \(f(m) \neq f(n)\), a contradiction. The same is true for \(m < 0\) and \(n \geq 0\).